#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //状态表示dp[i] 第i天后的最大利润
        //[0]有股票 [1]没有股票;[0]交易0次[1] 1次[2] 两次
        //状态机推导状态转移方程
        vector<vector<vector<int>>>dp(prices.size(),vector<vector<int>>(2,vector<int>(3,0)));
        dp[0][0][0]-=prices[0],dp[0][0][1]-=prices[0];
        for(int i=1;i<prices.size();i++){
            dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][1][0]-prices[i]);
            dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]+prices[i]);
            dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][1]-prices[i]);
            dp[i][1][2]=max(dp[i-1][1][2],dp[i-1][0][1]+prices[i]);
        }
        return *max_element(dp.back()[1].begin(),dp.back()[1].end());
    }
};